class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
      int n = triangle.size();
      if (n == 1) {
          return triangle[0][0];
      }
      vector<int> old(n);
      vector<int> cur(n);

      int result = 0;
      cur[0] = triangle[0][0];
      for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
          old[j] = cur[j];
        }
        for (int j = 0; j < i + 1; ++j) {
          if (j - 1 >= 0 && j < i) {
            cur[j] = triangle[i][j] + min(old[j - 1], old[j]);
          } else if (j - 1 >= 0) {
            cur[j] = triangle[i][j] + old[j - 1];
          } else {
            cur[j] = triangle[i][j] + old[j];
          }
          if (i == n - 1) {
            if (j == 0) {
              result = cur[j];
            } else {
              result = min(result, cur[j]);
            }
          }
        }
      }
      return result;
    }
};
